package com.mlh.binarytree;

import java.util.HashMap;

/**
 * @author 缪林辉
 * @date 2024/3/28 10:33
 * @DESCRIPTION
 */

// 给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树
public class BuildTree {
    HashMap<Integer,Integer> inorderMap=new HashMap<>();
    int rootIndex;
    int[] inorder;
    int[] postorder;
    public TreeNode method1(int[] inorder, int[] postorder) {
        this.inorder=inorder;
        this.postorder=postorder;
        rootIndex=postorder.length-1;
        // 为了高效查找根节点元素在中序遍历数组中的下标，我们选择创建哈希表来存储中序序列，即建立一个（元素，下标）键值对的哈希表。
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i],i);
        }
        return recursion(0,inorder.length-1);
    }

    // left为要构建子树的在中序数组的左边界，right为要构建子树的在中序数组的右边界
    public TreeNode recursion(int left,int right){
        //如果左边界大于右边界，代表该子树没有节点，返回null
        if(left>right){
            return null;
        }
        //寻找该树的根节点
        //这里寻找根节点是本题最难的点  实际上这边每次递归就减1就行
        //因为你会发现递归会将所有的右子树构造完，才会递归返回构造左子树，
        //这也是为什么只需要每次 rootIndex-1 就可以的原因
        int rootVal=postorder[rootIndex--];
        //在中序遍历中的下标
        int rootIndex = inorderMap.get(rootVal);
        TreeNode root = new TreeNode(rootVal);
        //注意这里有需要先创建右子树，再创建左子树的依赖关系。
        // 可以理解为在后序遍历的数组中整个数组是先存储左子树的节点，
        // 再存储右子树的节点，最后存储根节点，
        // 如果按每次选择「后序遍历的最后一个节点」为根节点，则先被构造出来的应该为右子树。

        //递归调用，返回该子树的右子树
        TreeNode rightNode = recursion(rootIndex + 1, right);
        //递归调用，返回该子树的左子树
        TreeNode leftNode = recursion(left, rootIndex - 1);
        root.left=leftNode;
        root.right=rightNode;
        return root;
    }
}
